package sort;

/**
 * 归并排序算法
 */
public class MergeSort {

    public static void sort(int[] arrSrc) {
        split(arrSrc, 0, arrSrc.length - 1);
    }

    //这是将数组拆分成小数组的方法，他是一个递归方法
    private static void split(int[] arrSrc, int iStartPos, int iEndPos) {
        if (iStartPos >= iEndPos) {
            return;
        }

        int iSplitPos = (iStartPos + iEndPos) / 2;
        split(arrSrc, iStartPos, iSplitPos);
        split(arrSrc, iSplitPos + 1, iEndPos);

        combine(arrSrc, iStartPos, iSplitPos, iEndPos);
    }

    //这是将两个不能再拆分的相邻小数组合并到一起的方法
    private static void combine(int[] arrSrc, int iStartPos, int iSplitPos, int iEndPos) {

        //创建一个能容纳两个数组数量总数的临时数组，用于存放排序后的内容
        int[] arrTemp = new int[iEndPos - iStartPos + 1];
        int i = iStartPos;
        int j = iSplitPos + 1;
        int k = 0;
        while (i <= iSplitPos && j <= iEndPos) {
            if (arrSrc[i] <= arrSrc[j]) {
                arrTemp[k++] = arrSrc[i++];
            } else {
                arrTemp[k++] = arrSrc[j++];
            }
        }

        //判断哪个数组已经用完
        int iLeftStart = i;
        int iLeftEnd = iSplitPos;
        if (j <= iEndPos) {
          iLeftStart = j;
          iLeftEnd = iEndPos;
        }

        //将剩余的数据加到数组的最后面
        for (i = iLeftStart; i <= iLeftEnd; i++) {
            arrTemp[k++] = arrSrc[i];
        }

        //将临时数组的数据复制到源数组
        for (i = 0; i <= iEndPos - iStartPos; i++) {
            arrSrc[i + iStartPos] = arrTemp[i];
        }
    }

    public static void main(String[] args) {
        int[] arrSrc = CommonUtil.createIntArray(20);
        CommonUtil.printArr(arrSrc);
        sort(arrSrc);
        CommonUtil.printArr(arrSrc);
    }

}
